import random
from Crypto.Util.number import *
import numpy as np
import gmpy2


n = gmpy2.mpz("24579139606784371097119450777505497559902788044390859486207103747911130645847199807655291463605216259630814564993059")

# n = p * q

P = (2441276631279438325107649016771386750283631250456176007047,
     518977588578348104829006572552789464653487828502604088614)
Q = (145209878471534003613216346594463133860677999091779831326,
     2012072911059587487946252884280697891223335402503553158653)

p = 1
x1, y1 = P
x2, y2 = Q

# 计算斜率, 由于这里的a是64个比特的随机数, 该值相对x1 ** 2和y1都非常渺小, 所以这里的a几乎可以忽略不计
real_lambda = 17225690631719878021193934692901207053184398017874402213888  # 25 * 8 = 200bits
# for i in range(10):
#      a = random.getrandbits(64)
#      _lambda = (3 * (x1 ** 2) + a) / (2 * y1)
#      if real_lambda == "":
#           real_lambda = _lambda
#      else:
#           print(int(real_lambda), real_lambda == _lambda)

print(long_to_bytes(17225690631719878021193934692901207053184398017874402213888))


# 对点进行加运算
def add_point(point1, point2):
     x1, y1 = point1
     x2, y2 = point2
     x3 = (real_lambda ** 2 - x1 - x2) % p
     y3 = (real_lambda * (x1 - x3) - y1) % p

     return (x3, y3)


# e = 0
# point = P
# while True:
#      point = add_point(P, point)
#      if point[0] == Q[0] and point[1] == Q[1]:
#           print(e)
#           break
#
#      e += 1
#      if e > 4294967295:
#           break


# 辗转相除法: 求a, b两个数的最大公因数, 欧几里德算法
# 一条解释比较好的视频: https://www.bilibili.com/video/BV19r4y127fu/?spm_id_from=333.337.search-card.all.click&vd_source=4e8dae3309c51bf6e4154dc50e6bb515
def gcd(a, b):
     if b == 0:
          return a
     else:
          return gcd(b, a % b)


# 扩展欧几里得计算逆元
# 加减乘满足交换律, 除法不满足, 所以引入了逆元的概念
# (a + b) % p = a % p + b % p
# (a * b) % p = (a % p * b % p) % p
# (a / b) % p != (a % p) / (b % p)
# 逆元的概念: 若a, p互质, 则存在一个整数x, 使得
# 1 / a = x % p, 则x称为b模p的乘法逆元, x = a-1
# 1 / a * a = (x * a) % p => 1 = (a * x) % p
# => a * x = -y * p + 1 => a * x + p * y = 1(已知a, p, 求解x, y)
# 一条解释比较好的视频: https://www.bilibili.com/video/BV1p34y1k7UM/?spm_id_from=333.337.search-card.all.click&vd_source=4e8dae3309c51bf6e4154dc50e6bb515
def exgcd(a, b):
    if b == 0:
        x = 1
        y = 0
        return x, y, a
    else:
        x, y, g = exgcd(b, a % b)
        return y, x - (a // b) * y, g

    return res

